package 回溯;

import java.util.LinkedList;
import java.util.List;

//93 复原ip地址
public class Solution5 {
    public List<String> restoreIpAddresses(String s) {
        dfs(0,0,s,new String[4]);
        return res;
    }
    List<String> res = new LinkedList();

    void dfs(int index, int segId, String s, String[] segment){
        if(index>=s.length()||segId>=4){
            if(index==s.length()&&segId==4)
                res.add(to_string(segment));
            return;
        }
        for(int i=1;i<=3;i++){
            if(index+i>s.length()) return;
            String sub = s.substring(index,index+i);
            if(check(sub)){
                segment[segId] = sub;
                dfs(index+i, segId+1, s, segment);
            }
        }
    }

    String to_string (String[] segment){
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<3;i++){
            sb.append(segment[i]+".");
        }
        sb.append(segment[3]);
        return sb.toString();
    }

    boolean check(String s){
        return (s.charAt(0)!='0'||s.equals("0"))&&Integer.parseInt(s)<256;
    }
}
